LeetCode 41. First Missing Positive

41. First Missing Positive(缺失的第一个正数)

链接

https://leetcode-cn.com/problems/first-missing-positive

题目

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3
示例 2:

输入: [3,4,-1,1]
输出: 2
示例 3:

输入: [7,8,9,11,12]
输出: 1
说明:

你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。

思路

比较难的一类数组题目,对于复杂度和空间都有要求,结果就需要多考虑很多东西。
首先先设置长度为len,那么优先考虑为1-len范围的数字,每次优先把这些数字放在应该放的位置上swap(nums, i, nums[i] - 1),之后对于数组进行遍历,如果该位置上的数字不符合条件,那么直接返回该位置应该有的数(数组号+1),如果遍历完了,那么就应该是数组长度+1.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
private static void swap(int nums[], int a, int b) {
int c = nums[a];
nums[a] = nums[b];
nums[b] = c;
}

public static int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0) {
return 1;
}
for (int i = 0; i < nums.length; i++) {
while (nums[i] > 0 && nums[i] < nums.length && nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}

for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
---本文结束,感谢阅读---